Termination w.r.t. Q of the following Term Rewriting System could not be shown:

Q restricted rewrite system:
The TRS R consists of the following rules:

g(x, 0) → 0
g(d, s(x)) → s(s(g(d, x)))
g(h, s(0)) → 0
g(h, s(s(x))) → s(g(h, x))
double(x) → g(d, x)
half(x) → g(h, x)
f(s(x), y) → f(half(s(x)), double(y))
f(s(0), y) → y
id(x) → f(x, s(0))

Q is empty.


↳ QTRS
  ↳ DependencyPairsProof

Q restricted rewrite system:
The TRS R consists of the following rules:

g(x, 0) → 0
g(d, s(x)) → s(s(g(d, x)))
g(h, s(0)) → 0
g(h, s(s(x))) → s(g(h, x))
double(x) → g(d, x)
half(x) → g(h, x)
f(s(x), y) → f(half(s(x)), double(y))
f(s(0), y) → y
id(x) → f(x, s(0))

Q is empty.

Using Dependency Pairs [1,13] we result in the following initial DP problem:
Q DP problem:
The TRS P consists of the following rules:

G(h, s(s(x))) → G(h, x)
G(d, s(x)) → G(d, x)
ID(x) → F(x, s(0))
F(s(x), y) → DOUBLE(y)
F(s(x), y) → F(half(s(x)), double(y))
HALF(x) → G(h, x)
F(s(x), y) → HALF(s(x))
DOUBLE(x) → G(d, x)

The TRS R consists of the following rules:

g(x, 0) → 0
g(d, s(x)) → s(s(g(d, x)))
g(h, s(0)) → 0
g(h, s(s(x))) → s(g(h, x))
double(x) → g(d, x)
half(x) → g(h, x)
f(s(x), y) → f(half(s(x)), double(y))
f(s(0), y) → y
id(x) → f(x, s(0))

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

↳ QTRS
  ↳ DependencyPairsProof
    ↳ QDP
      ↳ EdgeDeletionProof

Q DP problem:
The TRS P consists of the following rules:

G(h, s(s(x))) → G(h, x)
G(d, s(x)) → G(d, x)
ID(x) → F(x, s(0))
F(s(x), y) → DOUBLE(y)
F(s(x), y) → F(half(s(x)), double(y))
HALF(x) → G(h, x)
F(s(x), y) → HALF(s(x))
DOUBLE(x) → G(d, x)

The TRS R consists of the following rules:

g(x, 0) → 0
g(d, s(x)) → s(s(g(d, x)))
g(h, s(0)) → 0
g(h, s(s(x))) → s(g(h, x))
double(x) → g(d, x)
half(x) → g(h, x)
f(s(x), y) → f(half(s(x)), double(y))
f(s(0), y) → y
id(x) → f(x, s(0))

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
We deleted some edges using various graph approximations

↳ QTRS
  ↳ DependencyPairsProof
    ↳ QDP
      ↳ EdgeDeletionProof
        ↳ QDP
          ↳ DependencyGraphProof

Q DP problem:
The TRS P consists of the following rules:

G(h, s(s(x))) → G(h, x)
G(d, s(x)) → G(d, x)
F(s(x), y) → DOUBLE(y)
ID(x) → F(x, s(0))
HALF(x) → G(h, x)
F(s(x), y) → F(half(s(x)), double(y))
F(s(x), y) → HALF(s(x))
DOUBLE(x) → G(d, x)

The TRS R consists of the following rules:

g(x, 0) → 0
g(d, s(x)) → s(s(g(d, x)))
g(h, s(0)) → 0
g(h, s(s(x))) → s(g(h, x))
double(x) → g(d, x)
half(x) → g(h, x)
f(s(x), y) → f(half(s(x)), double(y))
f(s(0), y) → y
id(x) → f(x, s(0))

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
The approximation of the Dependency Graph [13,14,18] contains 3 SCCs with 5 less nodes.

↳ QTRS
  ↳ DependencyPairsProof
    ↳ QDP
      ↳ EdgeDeletionProof
        ↳ QDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ QDP
                ↳ QDPOrderProof
              ↳ QDP
              ↳ QDP

Q DP problem:
The TRS P consists of the following rules:

G(h, s(s(x))) → G(h, x)

The TRS R consists of the following rules:

g(x, 0) → 0
g(d, s(x)) → s(s(g(d, x)))
g(h, s(0)) → 0
g(h, s(s(x))) → s(g(h, x))
double(x) → g(d, x)
half(x) → g(h, x)
f(s(x), y) → f(half(s(x)), double(y))
f(s(0), y) → y
id(x) → f(x, s(0))

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
We use the reduction pair processor [13].


The following pairs can be oriented strictly and are deleted.


G(h, s(s(x))) → G(h, x)
The remaining pairs can at least be oriented weakly.
none
Used ordering: Combined order from the following AFS and order.
G(x1, x2)  =  G(x1, x2)
h  =  h
s(x1)  =  s(x1)

Lexicographic path order with status [19].
Precedence:
h > G2
s1 > G2

Status:
G2: [1,2]
s1: multiset
h: multiset

The following usable rules [14] were oriented: none



↳ QTRS
  ↳ DependencyPairsProof
    ↳ QDP
      ↳ EdgeDeletionProof
        ↳ QDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ QDP
                ↳ QDPOrderProof
                  ↳ QDP
                    ↳ PisEmptyProof
              ↳ QDP
              ↳ QDP

Q DP problem:
P is empty.
The TRS R consists of the following rules:

g(x, 0) → 0
g(d, s(x)) → s(s(g(d, x)))
g(h, s(0)) → 0
g(h, s(s(x))) → s(g(h, x))
double(x) → g(d, x)
half(x) → g(h, x)
f(s(x), y) → f(half(s(x)), double(y))
f(s(0), y) → y
id(x) → f(x, s(0))

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
The TRS P is empty. Hence, there is no (P,Q,R) chain.

↳ QTRS
  ↳ DependencyPairsProof
    ↳ QDP
      ↳ EdgeDeletionProof
        ↳ QDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ QDP
              ↳ QDP
                ↳ QDPOrderProof
              ↳ QDP

Q DP problem:
The TRS P consists of the following rules:

G(d, s(x)) → G(d, x)

The TRS R consists of the following rules:

g(x, 0) → 0
g(d, s(x)) → s(s(g(d, x)))
g(h, s(0)) → 0
g(h, s(s(x))) → s(g(h, x))
double(x) → g(d, x)
half(x) → g(h, x)
f(s(x), y) → f(half(s(x)), double(y))
f(s(0), y) → y
id(x) → f(x, s(0))

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
We use the reduction pair processor [13].


The following pairs can be oriented strictly and are deleted.


G(d, s(x)) → G(d, x)
The remaining pairs can at least be oriented weakly.
none
Used ordering: Combined order from the following AFS and order.
G(x1, x2)  =  G(x1, x2)
d  =  d
s(x1)  =  s(x1)

Lexicographic path order with status [19].
Precedence:
d > G2
s1 > G2

Status:
d: multiset
G2: [1,2]
s1: multiset

The following usable rules [14] were oriented: none



↳ QTRS
  ↳ DependencyPairsProof
    ↳ QDP
      ↳ EdgeDeletionProof
        ↳ QDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ QDP
              ↳ QDP
                ↳ QDPOrderProof
                  ↳ QDP
                    ↳ PisEmptyProof
              ↳ QDP

Q DP problem:
P is empty.
The TRS R consists of the following rules:

g(x, 0) → 0
g(d, s(x)) → s(s(g(d, x)))
g(h, s(0)) → 0
g(h, s(s(x))) → s(g(h, x))
double(x) → g(d, x)
half(x) → g(h, x)
f(s(x), y) → f(half(s(x)), double(y))
f(s(0), y) → y
id(x) → f(x, s(0))

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
The TRS P is empty. Hence, there is no (P,Q,R) chain.

↳ QTRS
  ↳ DependencyPairsProof
    ↳ QDP
      ↳ EdgeDeletionProof
        ↳ QDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ QDP
              ↳ QDP
              ↳ QDP

Q DP problem:
The TRS P consists of the following rules:

F(s(x), y) → F(half(s(x)), double(y))

The TRS R consists of the following rules:

g(x, 0) → 0
g(d, s(x)) → s(s(g(d, x)))
g(h, s(0)) → 0
g(h, s(s(x))) → s(g(h, x))
double(x) → g(d, x)
half(x) → g(h, x)
f(s(x), y) → f(half(s(x)), double(y))
f(s(0), y) → y
id(x) → f(x, s(0))

Q is empty.
We have to consider all minimal (P,Q,R)-chains.